import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * User: tsegelskyi
 * Date: 22.02.13
 * Time: 16:03
 */

public class Deque<Item> implements Iterable<Item> {
    private int N;
    private Node pre;
    private Node post;

    public Deque() {
        pre = new Node();
        post = new Node();
        pre.next = post;
        post.prev = pre;
    }

    private class Node {
        private Item item;
        private Node next;
        private Node prev;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void addFirst(Item item) {
        if (item == null)
            throw new NullPointerException();
        Node temp = new Node();
        temp.next = pre.next;
        temp.prev = pre;
        temp.item = item;
        pre.next.prev = temp;
        pre.next = temp;
        N++;
    }

    public void addLast(Item item) {
        if (item == null)
            throw new NullPointerException();
        Node temp = new Node();
        temp.next = post;
        temp.prev = post.prev;
        temp.item = item;
        post.prev.next = temp;
        post.prev = temp;
        N++;
    }

    public Item removeFirst() {
        if (N <= 0)
            throw new NoSuchElementException();
        Item item = pre.next.item;
        pre.next = pre.next.next;
        pre.next.prev = pre;
        N--;
        return item;
    }

    public Item removeLast() {
        if (N <= 0)
            throw new NoSuchElementException();
        Item item = post.prev.item;
        post.prev = post.prev.prev;
        post.prev.next = post;
        N--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private Node current = pre.next;
            private int index = 0;

            @Override
            public boolean hasNext() {
                return index < N;
            }

            @Override
            public Item next() {
                if (!hasNext())
                    throw new NoSuchElementException();
                Item item = current.item;
                current = current.next;
                index++;
                return item;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}
